package com.sunny.l58;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

/**
 * @Author zsunny
 * @Date 2018/9/13 16:50
 * @Mail zsunny@yeah.net
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] num = {1,1};
        System.out.println(solution.getSub(num, 3));

    }
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for(int i=0;i<Math.pow(2,num.length);i++){
            ArrayList<Integer> sub = getSub(num, i);
            if(null != sub)
                res.add(sub);
        }
        Collections.sort(res, (a,b)->{
            int i;
            for(i=0;i<a.size() && i<b.size();i++){
                if(a.get(i) == b.get(i))
                    continue;
                return a.get(i)-b.get(i);
            }
            if(i == a.size()){
                return -1;
            }else{
                return 1;
            }
        });
        return res;
    }
    public ArrayList<Integer> getSub(int[] num, int dig){
        ArrayList<Integer> list = new ArrayList<>();
        int len = num.length;
        Stack<Boolean> stack = new Stack<>();
        int cnt = 0;
        int m = 1;
        while (cnt<len){
            cnt++;
            if((dig&m) > 0)
                stack.push(true);
            else
                stack.push(false);
            m <<= 1;
        }
//        System.out.println(stack);
        boolean prev = true;
        for(int i=0;i<len;i++){
            boolean flag = stack.pop();
            if(!prev && flag && 0 != i && num[i] == num[i-1]){
                return null;
            }
            if(flag){
                list.add(num[i]);
            }
            prev = flag;
        }
        return list;
    }


}
